In today's information age, communication networks are used to transport vast amounts of information. As more and more information is carried over these communication networks, the various communication devices within the communication network, such as routers and switches, are called upon to process increasing amounts of data traffic. Often times, this data traffic includes data having different priority levels, and specifically different bandwidth requirements. Therefore, the various communication devices within the communication network must schedule data transmission opportunities for the data based upon, among other things, the relative bandwidth requirements of the data.
One well-known scheduling discipline is commonly referred to as Weighted Round Robin (WRR) scheduling. In WRR scheduling, each priority level is assigned a relative weight, and transmission opportunities are allocated for each priority level based upon the relative weights of the priority levels, using a round-robin technique to cycle between the priority levels.
Another well-known scheduling discipline is commonly referred to as Weighted Fair Queuing (WFQ) scheduling. In WFQ scheduling, transmission opportunities are allocated to the priority levels by computing a finishing time for each data transmission and scheduling data transmissions based on the computed finishing times. In WFQ scheduling, any unused bandwidth from one priority level is automatically reallocated to the other priority levels.
WRR scheduling and WFQ scheduling work well, and are relatively easy to implement, when the communication network uses fixed-length data transmissions (for example, in a cell-based communication network). However, scheduling data transmission opportunities in a frame-based communication network is more complex due to the variability of frame sizes. This variability of frame sizes can result in incorrect bandwidth allocation when WRR scheduling is used, and makes it difficult to compute finishing times when WFQ scheduling is used.
Thus, a need has remained for a scheduling discipline that is easy to implement in a frame-based communication network and is capable of dynamically reallocating any unused bandwidth from one logical communication channel to the other logical communication channels.